/*
 * vim:foldmethod=marker:
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>
#include <unistd.h>
#include <assert.h>

/* {{{ fancy Mergesort */
int
Mergesort__merge(int *p1, int *p2, long long unsigned *mc, const int depth,
                 const int left, const int mid, const int right)
{
	int *array, *cpyarray;
	register int i = left, j = mid + 1, s = left;

#ifdef D
	fprintf(stderr, "mc=%llu, depth=%d, left=%d, mid=%d, right=%d\n",
			*mc, depth, left, mid, right);
#endif

	//if (*mc & 1)
	if (depth & 1)
		array = p1, cpyarray = p2;
	else
		array = p2, cpyarray = p1;

	while (i <= mid && j <= right) {
		if (array[i] <= array[j]) {
			cpyarray[s++] = array[i++];
		} else {
			cpyarray[s++] = array[j++];
		}
	}

	while (i <= mid)
		cpyarray[s++] = array[i++];
	while (j <= right)
		cpyarray[s++] = array[j++];

	assert(i == mid + 1);
	assert(j == right + 1);
	assert(s == right + 1);

	++*mc;
	return 0;
}

int
Mergesort__main(int *a, int *b, long long unsigned *mc, const int depth,
                const int L, const int R)
{
	int M = (L + R) / 2;

	if (L < R) {
		Mergesort__main(a, b, mc, depth + 1, L, M);
		Mergesort__main(a, b, mc, depth + 1, M + 1, R);
		Mergesort__merge(a, b, mc, depth, L, M, R);
	}

	return 0;
}
/* }}} */

/*
 * wrapper func
 */
int
Mergesort(int *array, const int n)
{
	int *tmp_array;
	static long long unsigned merge_count = 0;
	int depth = 0;

	tmp_array = malloc(n * sizeof *tmp_array);
	(void) memcpy(tmp_array, array, n * sizeof *array);

	Mergesort__main(array, tmp_array, &merge_count, depth, 0, n - 1);

#ifdef D
	fprintf(stderr, "merge_count=%llu\n", merge_count);
#endif

	free(tmp_array);
	return 0;
}

int
main(int argc, char **argv)
{
	int n;
	int *a;
	register int i = 0;

	scanf("%d", &n);
	a = malloc(n * sizeof *a);

	for (i = 0; i < n; i++)
		scanf("%d", a + i);

	Mergesort(a, n);

	for (i = 0; i < n; i++)
		printf("%d%c", a[i], (i + 1 == n) ? '\n' : ' ');

	free(a);
	return 0;
}
